Potential applications of Self-Sorting Memory of the invention include operations in numerical analysis, such as matrix manipulation, correlation, and other computations commonly performed procedures in applied mathematics. Other potential uses of Self-Sorting Memory include data rearrangement of the contents of data files such as that required in relational data base management in preparation for join, intersection, or other operations on relations, and simply file sorting which is required in nearly every application of computing systems.
The reasons for such diversity of computations to which the Self-Sorting Memory of the invention may be applied are the well-known limitation of conventional single-processor computers when used for rearranging information, and the ubiquitous task of rearranging data in computer applications. it is possible with conventional random access memory components to prepare sorted files rapidly, with time required for fewer serial operations than is consumed with conventional computers.
The Self-Sorting Memory of the present invention has storage for N records and provides for simultaneous access to approximately 0(log N) of these records so that sorting of records can be carried out without the expenditure of any more time than is required for a single scan of the records for input to the memory followed by a second scan for output from the memory.
The Self-Sorting Memory of the present invention may be used as a normal random access memory in a general purpose computer. Computers may be constructed with the self-sorting feature built into the main memory, and incorporating appropriate control for the Self-Sorting Memory in their normal instruction set. Alternatively, the Self-Sorting Memory of the invention may be constructed as an add-on Self-Sorting Memory for existing computers whose control may best be accommodated through the computer's input/output system.
The Self-Sorting Memory system of the present invention is of the same general type as the system described in U.S. Pat. 4,131,947 which issued Dec. 26, 1978 to the present inventor However, unlike the system of the patent, the system of the invention is composed of identical Modules with words which make up the various records being distributed among the Modules so that each Module stores the same number of words. The restriction on the number of words in a record, implicit in the system described in the patent, is thus removed by this change.